home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / graphic / pvquan16.zip / QUANT / OCTREE.C < prev    next >
C/C++ Source or Header  |  1992-11-30  |  5KB  |  177 lines
  1. /************************************************************************
  2.  *                                                                      *
  3.  *                  Copyright (c) 1991, Frank van der Hulst             *
  4.  *                          All Rights Reserved                         *
  5.  *                                                                      *
  6.  * Authors:                                                             *
  7.  *      FvdH - Frank van der Hulst (Wellington, NZ)                     *
  8.  *                                                                      *
  9.  * Versions:                                                            *
  10.  *    V1.1 910626 FvdH - QUANT released for DBW_RENDER                  *
  11.  *    V1.2 911021 FvdH - QUANT released for PoV Ray                     *
  12.  *    V1.6 921023 FvdH - Produce multi-image GIFs                       *
  13.  *                     - Port to OS/2 IBM C Set/2                       *
  14.  *                                                                      *
  15.  ************************************************************************/
  16. /* This code implements the alogrithm described in:
  17.  * Graphic Gems edited by Andrew Glassner
  18.  * Article: A Simple Method for Color Quantisation:
  19.  *          Octree Quantisation, pg. 287 ff
  20.  * by:      Michael Gervautz, Werner Purgathofer
  21.  *          Technical University Vienna
  22.  *          Vienna, Austria
  23.  */
  24.  
  25. /* Written by wRZL (Wolfgang Stuerzlinger) */
  26.  
  27. /* This code is hereby placed in public domain */
  28.  
  29. #include <string.h>
  30. #include "quant.h"
  31. #include "octree.h"
  32.  
  33. #define RGB(r,g,b) ((((unsigned long)(b) << input_bits) | ((g) << input_bits)) | (r))
  34. #define TESTBIT(a,i) ( ((a) >> (i)) & 1)
  35. #define MAXDEPTH 7
  36.  
  37. static UINT size;
  38. static UINT reducelevel;
  39. static UINT leaflevel;
  40. static OCTREE tree;
  41. static OCTREE reducelist[MAXDEPTH + 1];
  42.  
  43. static unsigned char quant_r,    /* Originally a parameter for quant2(), */
  44.                             quant_g,    /* moved here to reduce stack usage */
  45.                             quant_b;
  46.  
  47. static char quant2(OCTREE tree)
  48. {
  49.     if (tree->leaf)   return(tree->colorindex);
  50.     else                    return(quant2(tree->next[
  51.                                 TESTBIT(quant_r, MAXDEPTH - tree->level) * 4 +
  52.                                 TESTBIT(quant_g, MAXDEPTH - tree->level) * 2 +
  53.                                 TESTBIT(quant_b, MAXDEPTH - tree->level)]));
  54. }
  55.  
  56. int pal_index(UCHAR *p)
  57. {
  58.     quant_r = p[RED];
  59.     quant_g = p[GREEN];
  60.     quant_b = p[BLUE];
  61.     return quant2(tree);
  62. }
  63.  
  64. static double init_Cfactor;
  65. static UINT init_col_num;
  66.  
  67. static void initpalette(OCTREE tree)
  68. {
  69.     UINT j;
  70.  
  71.     if (tree == NULL) return;
  72.     if (tree->leaf || tree->level == leaflevel) {
  73.         palette[init_col_num][RED]   = (char) ((init_Cfactor * tree->rgbsum.r) / tree->colorcount + 0.5);
  74.         palette[init_col_num][GREEN] = (char) ((init_Cfactor * tree->rgbsum.g) / tree->colorcount + 0.5);
  75.         palette[init_col_num][BLUE]  = (char) ((init_Cfactor * tree->rgbsum.b) / tree->colorcount + 0.5);
  76.         tree->colorindex = init_col_num;
  77.         tree->leaf = TRUE;
  78.         init_col_num++;
  79.     } else {
  80.         for (j = 0; j < 8; j++)
  81.             initpalette(tree->next[j]);
  82.     }
  83. }
  84.  
  85. UINT calc_palette(UINT i, double Cfactor)
  86. {
  87.     init_Cfactor = Cfactor;
  88.     init_col_num = i;
  89.     initpalette(tree);
  90.     return init_col_num;
  91. }
  92.  
  93.  
  94. static void newandinit(OCTREE *tree, UINT depth)
  95.     {
  96.     *tree = (OCTREE)calloc(1,sizeof(struct node));
  97.     if (*tree == NULL) {
  98.         printf("out of memory");
  99.         err_exit();
  100.         }
  101.     (*tree)->level = depth;
  102.     (*tree)->leaf = (depth >= leaflevel);
  103.     if ((*tree)->leaf)
  104.         size++;
  105.     }
  106.  
  107. static void getreduceable(OCTREE *node)
  108.     {
  109.     UINT newreducelevel;
  110.  
  111.     newreducelevel = reducelevel;
  112.     while (reducelist[newreducelevel] == NULL)
  113.         newreducelevel--;
  114.     *node = reducelist[newreducelevel];
  115.     reducelist[newreducelevel] =
  116.                 reducelist[newreducelevel]->nextreduceable;
  117.     }
  118.  
  119. static void makereduceable(UINT level,OCTREE node)
  120. {
  121.     node->nextreduceable = reducelist[level];
  122.     reducelist[level] = node;
  123. }
  124.  
  125. static void reducetree(void)
  126. {
  127.     OCTREE node;
  128.     UINT depth;
  129.  
  130.     getreduceable(&node);
  131.     node->leaf = 1;
  132.     size = size - node->children + 1;
  133.     depth = node->level;
  134.     if (depth < reducelevel) {
  135.         reducelevel = depth;
  136.         leaflevel = reducelevel + 1;
  137.     }
  138. }
  139.  
  140. static UCHAR insert_rgb[3];   /* Originally a parameter for inserttree(), moved
  141.                                         here to reduce stack usage */
  142.  
  143. static void inserttree(OCTREE *tree, UINT depth)
  144. {
  145.     UINT branch;
  146.  
  147.     if (*tree == NULL)
  148.         newandinit(tree,depth);
  149.     (*tree)->colorcount++;
  150.     (*tree)->rgbsum.r += insert_rgb[RED];
  151.     (*tree)->rgbsum.g += insert_rgb[GREEN];
  152.     (*tree)->rgbsum.b += insert_rgb[BLUE];
  153.     if ((*tree)->leaf == FALSE && depth < leaflevel) {
  154.         branch = TESTBIT(insert_rgb[RED],MAXDEPTH - depth) * 4 +
  155.                     TESTBIT(insert_rgb[GREEN],MAXDEPTH - depth) * 2 +
  156.                     TESTBIT(insert_rgb[BLUE],MAXDEPTH - depth);
  157.         if ((*tree)->next[branch] == NULL) {
  158.             (*tree)->children++;
  159.             if ((*tree)->children == 2)
  160.                 makereduceable(depth,*tree);
  161.         }
  162.         inserttree(&((*tree)->next[branch]), depth + 1);
  163.     }
  164. }
  165.  
  166. void generateoctree(void)
  167. {
  168.     reducelevel = MAXDEPTH;
  169.     leaflevel = reducelevel + 1;
  170.  
  171.     while (get_pixel(insert_rgb)) {
  172.         inserttree(&tree, 0);
  173.         if (size > MAXCOLORS - 1)        /* max number of colors ! */
  174.             reducetree();
  175.     }
  176. }
  177.